# 示例 1：

# 输入：s = "babad"
# 输出："bab"
# 解释："aba" 同样是符合题意的答案。
# 示例 2：

# 输入：s = "cbbd"
# 输出："bb"


class Solution:
    def longestPalindrome(self, s: str) -> str:
        if not s:
            return ""

        # 预处理：头尾加哨兵，字符间加 '#'
        T = "^#" + "#".join(s) + "#$"

        n = len(T)
        # 回文半径数组
        P = [0] * n
        # 中心和右边界
        C = R = 0

        for i in range(1, n - 1):
            mirror = 2 * C - i

            if i < R:
                P[i] = min(R - i, P[mirror])
            else:
                P[i] = 1

            # 尝试扩展
            while T[i + P[i]] == T[i - P[i]]:
                P[i] += 1

            # 更新中心和右边界
            if i + P[i] > R:
                C = i
                R = i + P[i]

        # 找到最长回文
        max_len = 0
        center = 0
        for i in range(1, n - 1):
            if P[i] > max_len:
                max_len = P[i]
                center = i

        start = (center - max_len) // 2
        return s[start : start + max_len - 1]


if __name__ == "__main__":
    solution = Solution()
    print(solution.longestPalindrome("babad"))
    print(solution.longestPalindrome("cbbd"))
    print(solution.longestPalindrome("a"))
    print(solution.longestPalindrome("ac"))
    print(solution.longestPalindrome("abc"))
    print(solution.longestPalindrome("abcd"))
    print(solution.longestPalindrome("abcde"))
    print(solution.longestPalindrome("abcdef"))
    print(solution.longestPalindrome("abcdefg"))
    print(solution.longestPalindrome("abcdefgh"))
    print(solution.longestPalindrome("abcdefghi"))
    print(solution.longestPalindrome("abcdefghij"))
    print(solution.longestPalindrome("abcdefghijk"))
